class Solution(object):
    #* 单调栈解法 O(n)
    #* 在一维数组中对每一个数找到第一个比自己小的元素
    #* 场景：在一维数组中找第一个满足某种条件的数为典型的单调栈应用场景！
    #* 针对此题：对于每一个柱子都要向右计算以其为高的矩形，当且仅当
    #*          遇到【第一个严格小】的元素时能够确定！
    #* 计算区域：高度为 heights[stack.pop()]
    #*          左侧阻挡柱子：stack[-1]
    #*          右侧阻挡柱子：i
    #*          宽度为：i-stack[-1]-1
    def largestRectangleArea(self, heights):  # O(n)
        """
        :type heights: List[int]
        :rtype: int
        """
        # 使用 Stack 以空间换时间
        stack = []  # 保存元素的下标
        s_max = 0
        i = 0
        while i < len(heights):
            if len(stack) == 0 or heights[i] > heights[stack[-1]]:
                stack.append(i)
                i += 1
            else:  # 遇到了严格小的元素
                i_ = stack.pop()
                s_ = heights[i_] * (i-stack[-1]-1 if stack else i)
                s_max = max(s_, s_max)
        while len(stack) > 0:
            i_ = stack.pop()
            s_ = heights[i_] * (i-stack[-1]-1 if stack else i)
            s_max = max(s_, s_max)
        return s_max
    
    
    #* 加入哨兵 (Sentinel) 以避免讨论特殊情况
    #* 左边的柱子因为比输入数组里所有元素都小，因此不会出栈，栈则不会为空；
    #* 右边的柱子，同理，能保证所有元素出栈，因此遍历完成后栈中无元素。
    def largestRectangleAreaSentinel(self, heights):
        heights = [0] + heights + [0]
        stack = [0]  # 保存元素的下标
        s_max = 0
        for i in range(1, len(heights)):
            while heights[i] < heights[stack[-1]]:
                curr_h = heights[stack.pop()]  # 必须先 pop
                curr_w = i-stack[-1]-1  # 直到左边最小柱 (中间可能有跳过下标)
                s_max = max(s_max, curr_h * curr_w)
            stack.append(i)
        return s_max


if __name__ == "__main__":
    soln = Solution()
    print(soln.largestRectangleArea([0]))
    print(soln.largestRectangleArea([1]))
    print(soln.largestRectangleArea([2,1]))
    print(soln.largestRectangleArea([2,1,5,6,4]))
    print(soln.largestRectangleArea([2,1,3]))
    print(soln.largestRectangleArea([2,4,3]))
    print(soln.largestRectangleArea([1,9,3]))
    print(soln.largestRectangleArea([7,1,9,3]))
    print(soln.largestRectangleArea([2,1,5,6,2,3]))
    print(soln.largestRectangleArea([1,2,5,2,1,5,5]))
    print(soln.largestRectangleArea([4,2,0,3,2,4,3,4]))  # 截断问题！
